1. Field of the Invention
The invention is related to the field of communications, and in particular, to routing communications over different connections based on the relative delay of the connections.
2. Description of the Prior Art
FIG. 1 illustrates a telephone network in the prior art. The telephone network includes telephone switches 100–102. Telephone switch 100 is coupled to telephone connections 110–112. Telephone switch 101 is coupled to telephone connections 111 and 113–114. Telephone switch 102 is coupled to telephone connections 112–113. At any given moment, the telephone network handles several calls over telephone connections 110–114.
Consider the routing of telephone calls from telephone switch 100 to telephone switch 101. Telephone switch 100 must decide whether to use telephone connection 111 or telephone connection 112. Telephone connection 111 is directly coupled to telephone switch 101, but telephone connection 112 also requires telephone switch 102 and telephone connection 113 to reach telephone switch 101. Thus, telephone connection 111 is typically more desirable than telephone connection 112.
Telephone switch 100 routes calls to telephone switch 101 over desirable telephone connection 111 until the connection reaches its maximum capacity. When telephone connection 101 reaches its maximum capacity, then telephone switch 100 routes additional calls over less desirable telephone connection 112. As calls terminate, telephone connection 111 falls below its maximum capacity. When telephone connection 101 falls below its maximum capacity, then telephone switch 100 again routes calls over telephone connection 101 until it reaches its maximum capacity. Thus, telephone connections 112–113 provide overflow routing for telephone connection 111.
FIG. 2 illustrates an Internet Protocol (IP) network in the prior art. The IP network includes IP routers 200–203. IP router 200 is coupled to IP connections 210–213. IP router 201 is coupled to IP connections 211 and 214–216. IP router 202 is coupled to IP connections 212 and 214. IP router 203 is coupled to IP connections 213 and 215. At any given moment, the IP network handles several IP packets over connections 210–216.
Consider the routing of IP packets from IP router 200 to IP router 201. IP router 200 must decide whether to use IP connection 211, IP connection 212, or IP connection 213. IP connection 211 is directly coupled to IP router 201. IP connection 212 requires IP router 202 and IP connection 214 to reach IP router 201. IP connection 213 requires IP router 203 and IP connection 215 to reach IP router 201. Thus, IP connection 211 is typically the more desirable connection to use.
IP router 200 routes packets to IP router 201 over desirable IP connection 211. IP connection 211 simply slows down when it becomes heavily loaded, and does not have a maximum capacity that causes IP router 200 to begin using IP connections 212 or 213. IP router 200 may use IP connections 211–213 in some proportional manner, but these proportions are not adaptively changed based on relative capacities. Unfortunately, IP connections 212 and 213 do not provide overflow routing for IP connection 211.
FIG. 3 illustrates the operation of a Transmission Control Protocol (TCP) based IP network. TCP/IP user A transfers packet #1 to the TCP/IP network for delivery to TCP/IP user B. The TCP/IP network routes packet #1 to TCP/IP user B. TCP/IP user A transfers packet #2 to the TCP/IP network for delivery to TCP/IP user B. Unfortunately, the delivery of packet #2 to TCP/IP user B is delayed.
In response to receiving and checking packet #1, TCP/IP user B transfers acknowledgement (ACK) #1 to the TCP/IP network for delivery to TCP/IP user A. TCP/IP user A transfers packet #3 to the TCP/IP network for delivery to TCP/IP user B. The TCP/IP network routes packet #3 to TCP/IP user B. The TCP/IP network routes ACK #1 to TCP/IP user A.
If packet #2 had been correctly received and checked, TCP/IP user B would have responded to TCP/IP user A with ACK #2. However in this example, packet #2 was delayed. In response to receiving and checking packet #3 without yet receiving packet #2, TCP/IP user B again transfers ACK #1 to the TCP/IP network for delivery to TCP/IP user A. Note that TCP/IP user B cannot transfer ACK #3 until all packets #1, #2 and #3 are correctly received and checked. The TCP/IP network routes the second ACK #1 to TCP/IP user A.
TCP/IP user A sets a timer when it transmits a packet and will re-transmit the packet if the corresponding ACK is not received before the timer times-out. In this example, ACK #1 for packet #1 is received by TCP/IP user A before the time-out, so no re-transmission for packet #1 is required. Since packet #2 is delayed, no ACK #2 has been sent and the timer in TCP/IP user A for packet #2 times out. In response to the time-out, TCP/IP user A re-transmits packet #2 to the TCP/IP network for delivery to TCP/IP user B. This time, the TCP/IP network routes packet #2 to TCP/IP user B without delay. In response to receiving and checking packet #2 and now having correct packets #1, #2, and #3, TCP/IP user B transfers ACK #3 to the TCP/IP network for delivery to TCP/IP user A. The TCP/IP network routes ACK #3 to TCP/IP user A. Subsequently, the original but delayed packet #2 finally arrives at TCP/IP user B and is thrown away.
Note that the delay in transferring the original packet #2 caused a packet mis-sequence at TCP/IP user B, and the mis-sequence caused a re-transmission of packet #2. The re-transmission wastes both user and network resources, so it is desirable to avoid TCP/IP transmission techniques that cause mis-sequencing. For this reason, IP routers typically route all packets going to the same destination over the same IP connection, so the packets generally experience the same delay and remain in sequence. Unfortunately, this technique can overload the IP connection and slow down packet transfer to unacceptable levels.